#include<utility>
#include<iostream>

//链表节点
struct ListNode {
  int key;
  int val;
  ListNode *next;
  ListNode() : key(0), val(0), next(nullptr) {}
  ListNode(int Key, int Val, ListNode *Next) : key(Key), val(Val), next(Next) {};
};
class LRU {
  friend std::ostream &operator<<(std::ostream &cout, LRU &lru);

 public:
  LRU() : size_(0), capacity_(0), list_(nullptr) {};
  LRU(int size = 0, int capacity = 0) : size_(size), capacity_(capacity) {};
  ~LRU() {
    ListNode *temp{nullptr};
    while (list_) {
      temp = list_->next;
      delete list_;
      list_ = temp;
    }
  }
  void put(int &key, int &value) {

    ListNode *result = find(key);

    if (result) {
      //如果已经存在
      result->val = value;
      update(result);
      return;
    }

    if (this->size_ < this->capacity_) {
      // 不存在，并且还有容量
      ListNode *head = new ListNode(key, value, list_);
      list_ = head;
      size_++;

      return;
    }

    //不存在且已满
    auto getTailFront = [=]() -> ListNode * {
      if (list_ == nullptr) return nullptr;

      ListNode *pre = list_;

      while (pre->next) {
        pre = pre->next;
      }

      return pre;
    };

    // 把尾结点置换为第一个结点
    ListNode *front = getTailFront();
    ListNode *res = front;
    update(res);

    //更改新的第一个结点的key 和value
    list_->key = key;
    list_->val = value;
  }
  bool get(int &key) {
    ListNode *result = find(key);
    if (result == nullptr) {
      return false;
    }

    update(result);
    return true;
  }

 private:
  int size_{0};
  int capacity_{0};
  ListNode *list_{nullptr};//离头越近越新

 private:
  void update(ListNode *node) {
    if (node->next == nullptr) return;// 判断是不是已经是头结点

    auto getFrontNode = [=]() -> ListNode * {
      ListNode *back = nullptr, *pre = list_;

      while (pre != node) {
        back = pre;
        pre = pre->next;
      }
      return back;
    };

    ListNode *front = getFrontNode();
    if (front == nullptr) return;

    front->next = node->next;
    node->next = list_;
    list_ = node;

    std::cout << "update successly\n";
  }
  ListNode *find(int &key) {

    //如果没有则返回 {nullptr,nullptr}
    ListNode *pre = list_, *back = nullptr;
    while (pre) {
      if (pre->key == key) {
        return pre;
      }
      back = pre;
      pre = pre->next;
    }
    return nullptr;
  }

};
std::ostream &operator<<(std::ostream &cout, LRU &lru) {
  ListNode *pre = lru.list_;
  while (pre) {
    cout << "[" << pre->key << ',' << pre->val << "]";
    pre = pre->next;
  }
  return cout;
}
int main() {
  LRU lru(0, 1);

  int key, value;
  for (int i = 0; i < 1; i++) {
    //std::cin >> key >> value;
    key = i + 1, value = i + 3;

    bool res = lru.get(key);

    lru.put(key, value);
  }
  std::cout << lru << std::endl;
  key = 7, value = 77;
  lru.put(key, value);
  std::cout << lru << std::endl;
}
